/*
96. [不同的二叉搜索树](https://leetcode.cn/problems/unique-binary-search-trees/description/)
辛泽豪
*/

code：



class Solution {
public:
    // 主函数，计算n个节点能构成的不同二叉搜索树的数量
    int numTrees(int n) {
        // 动态规划数组，dp[i]表示i个节点能构成的不同二叉搜索树的数量
        vector<int> dp(n + 1, 0);

        // 初始化基础情况
        dp[0] = 1;  // 空树也是一种二叉搜索树
        dp[1] = 1;  // 只有一个节点的树也是一种二叉搜索树

        // 从2到n计算每个dp[i]
        for (int i = 2; i <= n; i++) {
            // 对于每个i，枚举根节点的位置j
            for (int j = 0; j < i; j++) {
                // 左子树有j个节点，右子树有i-1-j个节点
                // 左右子树的不同组合数相乘即为当前根节点下的二叉搜索树数量
                dp[i] += dp[j] * dp[i - 1 - j];
            }
        }

        // 返回n个节点能构成的不同二叉搜索树的数量
        return dp[n];
    }
};